811D - Vladik and Favorite Game - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
char mp[105][105];
int dir[][2] = { 0,1,0,-1,1,0,-1,0 };
int vis[105][105];
int done = 0;
int n, m;
struct node
{
	int x;
	int y;
	bool operator ==(const node& a)const
	{
		return a.x == x && a.y == y;
	}
};
struct bfsnode
{
	int x;
	int y;
	int idx;
	int fa;
	int dir;
}arr[10005];
int bfs(int x, int y)
{
	int idx = 0;
	queue<bfsnode>q;
	bfsnode st;
	vis[x][y] = 1;
	st = { x,y,idx++,-1,-1 };
	q.push(st);
	arr[st.idx] = st;
	while (!q.empty())
	{
		bfsnode temp = q.front();
		q.pop();
		if (mp[temp.x][temp.y] == 'F')
		{
			return temp.idx;
		}
		for (int i = 0; i < 4; i++)
		{
			int tx = temp.x + dir[i][0];
			int ty = temp.y + dir[i][1];
			if (tx<1 || tx>n || ty<1 || ty>m || vis[tx][ty] || mp[tx][ty] == '*')
				continue;
			vis[tx][ty] = 1;
			bfsnode cur;
			cur = { tx,ty,idx++,temp.idx,i };
			arr[cur.idx] = cur;
			q.push(cur);
		}
	}
}
node query(int dir)
{
	if (dir == 0)
		cout << 'R' << endl;
	else if (dir == 1)
		cout << 'L' << endl;
	else if (dir == 2)
		cout << 'D' << endl;
	else if (dir == 3)
		cout << 'U' << endl;
	node p;
	cin >> p.x >> p.y;
	return p;
}
bool checklr(int x,int y,int dir)
{
	node a = { x,y };
	node b = query(dir);
	if (a == b)
	{
		return true;
	}
	else
	{
		query(1-dir);
		return false;
	}
}
bool checkud(int x,int y,int dir)
{
	node a = { x,y };
	node b = query(dir);
	if (a == b)
		return true;
	else
	{
		query(5-dir);
		return false;
	}
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int swapLR = -1;
	int swapUD = -1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> mp[i][j];
		}
	}
	int i=bfs(1, 1);
	vector<int>route;
	while (arr[i].fa != -1)
	{
		route.push_back(arr[i].dir);
		i = arr[i].fa;
	}
	route.push_back(-1);
	reverse(route.begin(), route.end());
	int maxstep = route.size();
	int x = 1, y = 1;
	if (route[1] == 0)
	{
		if (checklr(x, y, 0))
		{
			swapLR = 1;
		}
		else
		{
			swapLR = 0;
		}
		int pos = 0;
		for (int i = 1; i < maxstep; i++)
		{
			if (route[i] <= 1)
			{
				int d = swapLR ? 1 - route[i] : route[i];
				query(d);
				x += dir[route[i]][0];
				y += dir[route[i]][1];
			}
			else
			{
				pos = i;
				break;
			}
		}
		if (checkud(x, y,route[pos]))
		{
			swapUD = 1;
		}
		else
		{
			swapUD = 0;
		}
		for (int i = pos; i < maxstep; i++)
		{
			if (route[i] == 1 || route[i] == 0)
			{
				int d = swapLR ? 1 - route[i] : route[i];
				query(d);
				x += dir[route[i]][0];
				y += dir[route[i]][1];
			}
			if (route[i] == 2 || route[i] == 3)
			{
				int d = swapUD ? 5 - route[i] : route[i];
				query(d);
				x += dir[route[i]][0];
				y += dir[route[i]][1];
			}
		}
	}
	else if (route[1] == 2)
	{
		if (checkud(x, y, 2))
		{
			swapUD = 1;
		}
		else
		{
			swapUD = 0;
		}
		int pos = 0;
		for (int i = 1; i < maxstep; i++)
		{
			if (route[i]==2||route[i]==3)
			{
				int d = swapUD? 5 - route[i] : route[i];
				query(d);
				x += dir[route[i]][0];
				y += dir[route[i]][1];
			}
			else
			{
				pos = i;
				break;
			}
		}
		if (checklr(x, y, route[pos]))
		{
			swapLR = 1;
		}
		else
		{
			swapLR = 0;
		}
		for (int i = pos; i < maxstep; i++)
		{
			if (route[i] == 1 || route[i] == 0)
			{
				int d = swapLR ? 1 - route[i] : route[i];
				query(d);
				x += dir[route[i]][0];
				y += dir[route[i]][1];
			}
			if (route[i] == 2 || route[i] == 3)
			{
				int d = swapUD ? 5 - route[i] : route[i];
				query(d);
				x += dir[route[i]][0];
				y += dir[route[i]][1];
			}
		}
	}
	return 0;
}